`
https://leetcode.cn/problems/maximum-partition-factor/
`

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPartitionFactor = function (points) {
  const n = points.length
  if (n === 2) return 0

  // 给定 k ，是否能将所有点分为两个非空组
  // 且同一组内的所有无序点对之间的曼哈顿距离 >= k
  const check = (k) => {
    // 假设可以按照要求分成两组，那么不同组的任意点对的曼哈顿距离都是 < k 的
    // 所以可以保留 < k 的曼哈顿距离，视为边，判断只有这些边的图是否是二分图

    // 0 表示没访问，1 和 -1 表示颜色
    const colors = new Array(n).fill(0)

    const dfs = (x, c) => {
      colors[x] = c
      const [x1, y1] = points[x]
      for (let y = 0; y < n; y++) {
        const [x2, y2] = points[y]
        if (y === x || Math.abs(x1 - x2) + Math.abs(y1 - y2) >= k) {
          continue
        }
        if (colors[y] === c || colors[y] === 0 && !dfs(y, -c)) {
          return false // 不是二分图
        }
      }
      return true
    }

    // 可能有多个联通块
    for (let i = 0; i < n; i++) {
      const c = colors[i]
      if (c === 0 && !dfs(i, 1)) {
        return false
      }
    }
    return true
  }

  let maxDist = -Infinity
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const [xi, yi] = points[i]
      const [xj, yj] = points[j]
      maxDist = Math.max(maxDist, Math.abs(xi - xj) + Math.abs(yi - yj))
    }
  }

  let left = 0, right = maxDist + 1
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      left = mid
    } else {
      right = mid
    }
  }
  return left
};